package hash;


public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] arr;
    public int usedSize;//存放元素的个数

    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBuck(){
        arr = new Node[10];
    }

    public void put(int key,int val){
        int index = key % arr.length;
        // 遍历index下标的链表是否存在key,存在更新value,不存在尾插法插入数据
        Node cur = arr[index];
        while(cur != null){
            if (cur.key == key){
                //更新val
                cur.val = val;
                return;
                }
                cur = cur.next;
            }

            // 链表遍历完了,没有找到key
            // 头插法
            Node node = new Node(key,val);
            node.next = arr[index];
            arr[index] = node;
            usedSize++;

            if (doLoadFactor() > DEFAULT_LOAD_FACTOR){//如果负载因子超出,扩容
                // 扩容之后要重新哈希
                //arr = Arrays.copyOf(arr,2*arr.length);
                resize();


            }
    }


    private float doLoadFactor(){
        return usedSize*1.0f / arr.length;
    }

    private void resize(){
        Node[] newArr = new Node[2*arr.length];
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            while (cur != null){//遍历每个数组元素
                Node tmp = cur.next;//保存next
                int newIndex = cur.key % newArr.length;//新的数组下标
                //采用头插法插入到新数组的 newIndex 下标
                cur.next = newArr[newIndex];
                newArr[newIndex] = cur;
                cur = tmp;
            }
        }
        arr = newArr;
    }

    public int get(int key){
        int index = key % arr.length;
        Node cur = arr[index];
        while (cur != null){
            if (cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }



}
